import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 * User: 86189
 * Date: 2022-07-05
 * Time: 23:09
 */
//大根堆
//时间复杂度O(nlogk)，空间复杂度O(k)
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //要求无序就可以使用大根堆比较好
        if ( k == 0 ) {
            return new ArrayList<Integer>();
        }
        //默认小根堆，改为大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>( new Comparator<Integer>() {
            @Override
            public int compare (Integer o1 , Integer o2) {
                return o2 - o1;
            }
        } );
        for (int i = 0; i < input.length; i++) {
            if ( i < k ) {
                pq.add( input[i] );
            } else {
                if ( input[i] < pq.peek() ) {
                    pq.poll();
                    pq.add( input[i] );
                }
            }
        }
        return new ArrayList<>( pq );
    }
}
